/* 
   KARAN GUPTA - 2010037
   LIST IMPLEMENTATION USING LINKED LISTS
*/

# include <stdio.h>
# include <stdlib.h>

struct node
{
  int value;
  struct node *next;
}*first,*last; /* First is a global pointer pointing to the first node of the linked list and similarly last to the last*/

append (int num)
{
  struct node *temp,*r;
  temp = malloc (sizeof (struct node));
  temp -> value = num;
  r = last;
  if (first == NULL )
  {
     first= temp;
     last = temp;
     first->next = NULL;
  }
  else
  { 
     last->next = temp;
     last = temp;
  }
}

insert (int num,int loc)
{
  struct node *back,*front,*temp;
  temp = malloc(sizeof(struct node));
  temp->value = num;
  back = first;
  front = first;
  if ( loc == 1 )
  {
    if ( first == NULL )
    {
      append (num);
    }
    else
    {
      temp->next = first;
      first = temp;
    }
  }
  else 
  {
    int i = 1;
    while (i != loc)
    {
      back = front;
      front = front->next;
      i++;
    }
    back->next = temp;
    temp->next = front;
  }
}

delete (int num)
{
  struct node *temp, *r;
  temp = first;
  while ( temp != NULL )
  {
    if (temp->value == num)
    {
      if (temp == first)
       {
        first = temp->next;
        free(temp);
        return;
       }
      else
       {
        r->next = temp->next;
        free(temp);
        return;
       }
    }
    else
    {
      r = temp;
      temp= temp->next;
    }
  }
    printf("Element %d not found\n", num);
    getchar();getchar();
    system("clear");
}

int pop (int pos)
{
  struct node *temp, *prev;
  int i;
  temp = first;
  for ( i=1; i<pos; i++)
  {
    prev = temp;
    temp = temp->next;
  }
  if (temp == first)
  {
    first = temp->next;
    return temp->value;
    free(temp);
  }
  else
  {
    prev->next = temp->next;
    return temp->value;
    free(temp);
  }
}

indexofnum (int num)
{
  struct node *temp;
  int place = 1;
  temp = first;
  while (temp!=NULL && temp->value != num)
  {
    place++;
    temp = temp->next;
  }
  if ( place >= 1 && place<=noofelements() )
    printf("Element %d, first found at position %d\n", num, place);
  else
    printf("No such element!\n");    
}

count (int num)
{
  struct node *temp;
  int count = 0;
  temp = first;
  while( temp != NULL )
  {
    if (temp->value == num)
      count++;
    temp = temp->next;
  }
  printf("%d appears %d number of times\n",num,count);
}

sort ()
{
  int i,j,temp;
  struct node *p,*q;
  p = first;
  for ( i = 0 ; i < noofelements() - 1 ; i++ )
  {
    q = p -> next;
    for ( j = i + 1 ; j < noofelements() ; j++ )
    {
       if ( p -> value > q -> value )
       {
	temp = p -> value ;
	p -> value= q -> value ;
	q -> value = temp ;
       }
       q = q -> next ;
    }
    p = p -> next ;
  } 
}

reverse ()
{
  struct node *i,*n1,*n2;
  i = first;
  n1 = NULL;
  while ( i != NULL )
  {
    n2 = n1;
    n1 = i;
    i = i->next;
    n1->next = n2;
  }
  first = n1;  
}

display ()
{
  struct node *temp;
  temp = first;
  if (temp == NULL)
  {
    printf ("List is empty!\n");
  }
  else
  {
    printf ("[ ");
    while ( temp!=NULL )
   {
      printf ("%d,",temp->value);
      temp = temp->next;
    }
    printf (" ]\n");
  }
}

int noofelements()
{
  struct node *temp;
  int count = 0;
  temp = first;
  while (temp!=NULL)
  {
    count++;
    temp = temp->next;
  }
  return count;
}

void main()
{
  system("clear");
  int choice;
  while (1)
  { 
    printf("\n1.  APPEND - Add an item to the end of the list\n");
    printf("2.  INSERT - Insert an item at a given position\n");
    printf("3.  REMOVE - Remove the first item from the list whose value is x\n");
    printf("4.  POP    - Remove the item at the given position in the list, and return it\n");
    printf("5.  INDEX  - Return the index in the list of the first item whose value is x\n");
    printf("6.  COUNT  - Return the number of times x appears in the list\n");
    printf("7.  SORT   - Sort the items in the list\n");
    printf("8.  REVERSE- Reverse the elements of the list\n");
    printf("9.  EXIT   - End the program\n");
    printf("\n");
    printf("LIST : ");
    display();
    printf("\n");
    printf("Enter choice number: ");
    scanf ("%d",&choice);

      switch(choice)
    {
        case 1:
      {
        int num;
        printf("Enter the number to be appended: ");
        scanf("%d",&num);
        append(num);
        system("clear");
        break;
      }
        case 2:
      {
        int num, loc,k;
        int total = noofelements();
        printf("Enter the number to be inserted: ");
        scanf("%d",&num);
        printf("Enter the location where it needs to be inserted: ");
        scanf("%d",&loc);
        if (loc>0 && loc<=total+1)
        {
          insert(num,loc);
	  system("clear");
        }
        else
        {
          printf("The location entered doesn't exist!\n");
          getchar();getchar();
          system("clear");
        }
        break;
      }  
        case 3:
      {
        int num;
        printf("Enter the number to be removed: ");
        scanf("%d",&num);
        delete(num);
        system("clear");
        break;
      }
         case 4:
      {
        int pos,num;
        int total = noofelements();
        printf("Enter the position which has to be popped: ");
        scanf("%d",&pos);
        if (pos>0 && pos<=total)
        {
          num = pop(pos);
          printf("The popped number is %d\n",num);
          getchar();getchar();
          system("clear");
        }
        else
        {
          printf("The location entered doesn't exist!\n");
          getchar();getchar();
          system("clear");
        }
        break;
      }
        case 5:
      {
        int num;
        printf("Enter the number whose index needs to be returned: ");
        scanf("%d",&num);
        indexofnum(num);
        getchar();getchar();
        system("clear");
        break;
      }
        case 6:
      {
        int num;
        printf("Enter the number which needs to be counted: ");
        scanf("%d",&num);
        count(num);
        getchar();getchar();
        system("clear");
        break;
      }  
        case 7:
      {
        sort();
        system("clear");
        break;
      }
        case 8:
      {
        reverse();
	system("clear");
        break;
      }
      case 9:
      {
        exit(0);
        break;
      }
        default:
      {
        printf("Wrong Choice Entered!\n");
        getchar();getchar();
        system("clear");
        break;
      }
    }
  }
  free (first);
  free (last);
} 
